//
// Description: 74. 搜索二维矩阵
// Created by Loading on 2025/4/21.
//

#include <bits/stdc++.h>

using namespace std;

bool searchMatrix(vector<vector<int>> &matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();

    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int x = matrix[mid / n][mid % n];
        if (x > target) {
            r = mid - 1;
        } else if (x < target) {
            l = mid + 1;
        } else {
            return true;
        }
    }

    return false;
}

int main() {
    vector<vector<int>> matrix{{1,  3,  5,  7},
                               {10, 11, 16, 20},
                               {23, 30, 34, 60}};
    int target = 13;

    auto res = searchMatrix(matrix, target);

    cout << res << endl;

    return 0;
}
